This invention relates to automatic reclamation of allocated, but unused memory, or garbage, in a computer system that uses a space-incremental garbage collector to process an object space concurrently with the operation of application threads. Memory reclamation may be carried out by a special-purpose garbage collection algorithm that locates and reclaims dynamically assigned memory (called “heap” memory) that is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compact and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms for Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
However, many of the aforementioned garbage collection techniques often lead to long and unpredictable delays because normal application thread processing must be suspended during the garbage collection process (called “stop the world” or STW processing) and these collectors at least occasionally scan the entire heap memory. Therefore, these techniques are generally not suitable in situations, such as real-time or interactive systems, where non-disruptive behavior is of greatest importance. Several other conventional techniques are typically used to alleviate these delays.
In accordance with one such technique, some garbage collectors operate mostly concurrently with the operation of the application threads. For example, in collectors that mark reachable objects by following references from one object to another, the marking may be done by threads that operate mostly concurrently with the application threads. Memory associated with objects that remain unmarked at the end of the marking operation can then be reclaimed sometimes also concurrently with application execution.
Another solution for limiting pause times is to use a space incremental garbage collector. In such a collector, during each successive collection increment, which typically (but not necessarily) is performed during a single pause in the application execution, the collector processes a small portion, or “collection set”, of the heap memory. This approach can often limit pause time adequately without the complexity of requiring the collector to operate concurrently with the application.
However, all of the aforementioned collectors introduce pauses of varying duration. Often the duration of the pauses is difficult to predict so that for some applications these collectors present difficulties. Thus, some collectors allow the user to specify the amount of garbage collection time relative to application execution time so that the worst-case duration of pauses can be predicted. For example, a user might specify that x milliseconds of application execution are to be followed by y milliseconds of garbage collection time. An example of such a garbage collector is described in an article entitled “A Real-time Garbage Collector with Low Overhead and Consistent Utilization”, D. F. Bacon, P. Cheng and V. T. Rajan, Conference Record of the Thirtieth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, New Orleans, La. January 2003.
Another similar approach called “Garbage-First” garbage collection uses a space-incremental collection technique and also performs operations, such as marking, concurrently with the operation of the application. This collector allows a user to specify a “soft” real-time goal that garbage collection will consume a maximum of MaxGC milliseconds out of any application execution time window of duration TW milliseconds. This goal is illustrated in the graphs shown in FIGS. 1, 2A and 2B. In these graphs, the horizontal axis represents time increasing towards the right. The vertical axis represents garbage collector overhead increasing in an upwards direction. As shown in FIG. 1, the real-time goal is based on a window 100 of duration TW. This window slides to the right (in the direction of increasing time). For example, the window is shown at position 102 after an elapsed time of S milliseconds.
In FIG. 2A, a STW pause 202 of time duration MaxGC is illustrated as if occurring in time window 200. In this illustration a single pause consumes the entire allotted garbage collection time. Since all application threads are stopped during the pause, the garbage collector overhead rises to 100 percent. A more frequent occurrence is shown in FIG. 2B in which three garbage collection STW pauses 206, 208 and 210 occur in a time window 204 of TW milliseconds duration. In this case the real-time goal would be to make the time durations of these windows less than the allotted garbage collection time: D1+D2+D3≦MaxGC.
Although the collector does not guarantee to meet this real-time goal, it attempts to do so with high probability. To attempt to achieve the real-time goal, the collector accounts for current garbage collection activity and then schedules future activity. To schedule future activity, the collector deals with heap regions and has a model of the time cost of collecting a particular heap region as a function of quickly-measured properties of that region. Using these time costs, the collector can choose a set of heap regions that can be collected within a given pause time limit (with high probability). Further, collection is delayed if necessary (and possible) until a pause of a given duration can be accommodated to avoid violating the real-time goal.
However, in meeting the real-time goal, the garbage first garbage collector only considers pauses and does not take into account the amount of concurrent marking and summarizing that actually takes place during its operation. Consequently, its predictions are not as accurate as they could be.